#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

// 堆排序
// 堆排序的时间复杂度是O(nlogn)，空间复杂度是O(1)，不稳定排序
// 堆化时间是O(logn)，，排序时间O(n),空间复杂度是O(1)，不稳定排序

// 大根堆的下沉操作
static void shiftdown_gt(int arr[], int i, int len) {
    int temp = arr[i];
    int child = 2 * i + 1;
    while (child < len) {
        if (child + 1 < len && arr[child] < arr[child + 1]) {
            child++;
        }
        // 如果父节点大于子节点，下沉结束，原因是每次调整的时候都已经决定了子节点其子树中最大的节点
        // 如果已经比子节点大了，不需要在和其子孙比较了
        if (temp >= arr[child]) {
            break;
        }
        arr[i] = arr[child];
        // 当前节点和子节点比较完成后
        i = child;
        child = 2 * i + 1;
    }
    arr[i] = temp;
}

void HeapSort(int arr[], int len) {
    // 建堆
    // 从最边缘非叶子节点到的父节点开始针对单一子树进行下沉操作，直到根节点
    for (int i = len / 2 - 1; i >= 0; i--) {
        shiftdown_gt(arr, i, len);
    }

    // 排序
    // 将堆顶元素和最后一个元素交换，然后对堆顶元素进行下沉操作
    // 每次最后一个元素都是最大的，所以长度-1，不去对最后一个元素进行操作
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        shiftdown_gt(arr, 0, i);
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     HeapSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }